1. Field of the Invention
One or more embodiments of the present invention relate to a method, medium, and system for video encoding, and more particularly, to a method, medium, and system for video encoding with a motion estimation method, medium, and system with fast motion estimation.
2. Description of the Related Art
In order to achieve compression of video data, temporal redundancy between adjacent images in a corresponding video sequence can be removed. To remove such temporal redundancy, correlation between the adjacent images should be determined and block-matching motion estimation applied.
Here, since motion estimation between a current image and a reference image is the most intensive computational part of video encoding, efficient motion estimation has emerged as one of the more important tasks in video encoding. Accordingly, various block-based motion estimation techniques have been developed.
First, in a full search technique, costs of all blocks in a search range of a reference image are calculated and the block having the minimum cost is searched for. However, such a process requires a large number of computations, which prevents video encoding from being performed in real time. To solve this problem, fast block-matching motion estimation techniques, such as a pattern-based global search and a pattern-based local search, have been suggested. Examples of pattern-based global searches include a three-step search, a new three-step search, and a four-step search. Examples of pattern-based local searches include a diamond search and a hexagon search. In the pattern-based local search, unlike in the pattern-based global search, a search is made in only a part of a search range and thus a search for a local minimum can be performed quickly. In the following description, the three-step search and the diamond search will be used as examples of the pattern-based global search and the pattern-based local search, respectively.
FIG. 1 illustrates such a conventional three-step search through three illustrations.
Here, the sample image 11 of FIG. 1 shows a conventional three-step search algorithm. In a first step, costs of blocks specified by 9 points forming the largest area around a central point of a search range of a reference picture are calculated. In a second step, costs of blocks specified by 9 points forming the middle area around a point having the minimum cost among the costs calculated in the first step are calculated. In a third step, costs of blocks specified by 9 points forming the smallest area around a point having the minimum cost among the costs calculated in the second step are calculated. A block specified by a point having the minimum cost among the costs calculated in the third step is determined to be the best matching block of the current block.
The sample image 12 of FIG. 1 shows a distribution map of the calculated costs according to the three-step search algorithm. In particular, in the sample image 12, as the cost of a block decreases, the illustration of the block is darkened. The sample graph 13 of FIG. 1 shows the relationship between search range and cost. It can be seen from the sample graph 13 that the sample picture 12 has one global minimum.
Similarly, FIG. 2 illustrates such a conventional diamond search through three illustrations.
The sample image 21 of FIG. 2 shows a conventional diamond search algorithm. In a first step, costs of blocks specified by 9 points forming a diamond pattern around a central point of a search range of a reference picture are calculated. If the central point has the minimum cost among the costs calculated in the first step, a second step is skipped and a third step is performed. Otherwise, the second step is performed. In the second step, costs of blocks specified by 9 points forming the diamond pattern around a point having the minimum cost among the costs calculated in the first step are calculated. If the central point is the point having the minimum cost among the costs calculated in the second step, the third step is performed. Otherwise, the second step is repeated until the respective central point is the point having the minimum cost. In the third step, costs of blocks specified by 5 points forming the diamond pattern around the point having the minimum cost among the costs calculated in the second step are calculated. The block specified by a point having the minimum cost among the costs calculated in the third step is determined to be the best matching block of the current block.
The sample image 22 of FIG. 2 shows a distribution map of the calculated costs according to this conventional diamond search algorithm. In particular, in the sample image 22, as the cost of a block decreases, the illustration of the block is darkened. The sample graph 23 of FIG. 2 shows the relationship between search range and cost. Here, it can be seen from the sample graph 23 that the sample image 22 has three local minima.
In video having small and smooth motion changes, a block matching cost generally has one global minimum or local minimum, i.e., a uni-modality feature. On the other hand, in video having large motion changes, a block matching cost has a plurality of local minima, i.e., a multi-modality feature.
In the three-step search algorithm illustrated in FIG. 1, since one global minimum is searched for in the entire search range, it is not difficult to search for a true minimum in the search range of a video having large motion changes. However, in the diamond search algorithm illustrated in FIG. 2, since one local minimum is searched for in a portion of the search range, a point in the search range, which is not a true matching point, may be selected as a local minimum unless a starting point is selected as being sufficiently close to a global minimum in a video having large motion changes, i.e., a video whose block matching cost has the multi-modality feature. For example, if a starting point I(A) is selected, the diamond search algorithm is trapped with an inappropriate local minimum A. If a starting point I(B) is selected, the diamond search algorithm is trapped with an inappropriate local minimum B.